package com.example.hot100;

import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *  编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *  你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *  此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 *
 *  示例 1：
 *  输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 *
 *  示例 2：
 *  输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 *
 *  示例 3：
 *  输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 *
 *  示例 4：
 *  输入：s = "abc3[cd]xyz"
 * 输出："abccdcdcdxyz"
 */
public class Leetcode394_DecodeString {
    public static void main(String[] args) {

//        StringBuilder sb = new StringBuilder();
//        sb = sb.append("a");
//        sb = sb.append("b");
//        sb = sb.append("c");
//        sb = sb.append(sb);
//        System.out.println(sb.toString());
//        System.out.println(sb.reverse().toString());

        String str = "3[a]2[bc]";

        str = "3[a2[c]]";
        System.out.println(new Solution().decodeString(str));
    }

    static class Solution {
        public String decodeString3(String s) {
            return null;
        }

        int ptr = 0;
        public String decodeString2(String s) {
            return null;
        }

        public String decodeString1(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return "";
            char[] chars = s.toCharArray();
            Deque<String> stack = new LinkedList<>();

            while (ptr < len) {
                if (Character.isDigit(chars[ptr])) { // 当前元素的数字，向后遍历直到是该字符不是数字为止
                    String numStr = getNumStr(chars);
                    stack.addLast(numStr);
                } else if (Character.isLetter(chars[ptr]) || chars[ptr] == '[') {
                    stack.addLast(chars[ptr++] + "");
                } else { // 遇到']'开始出栈，一直到栈顶为'['
                    ++ptr;
                    LinkedList<String> sub = new LinkedList<>();
                    while (!"[".equals(stack.peekLast())) {
                        sub.addFirst(stack.removeLast());// 头插不用再进行一次翻转
                    }
                    stack.removeLast();// 左括号出栈
                    // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                    int count = Integer.parseInt(stack.removeLast());
                    StringBuffer tmpSb = new StringBuffer();
                    String str = String.join("", sub);
                    // 构造字符串
                    while (count-- > 0) {
                        tmpSb.append(str);
                    }
                    // 将构造好的字符串入栈
                    stack.addLast(tmpSb.toString());
                }
            }

            return String.join("", stack);
        }

        private String getNumStr(char[] chars) {
            StringBuilder sb = new StringBuilder();
            while (Character.isDigit(chars[ptr])) {
                sb.append(chars[ptr++]);
            }
            return sb.toString();
        }

        public String decodeString(String s) {
            return decodeString1(s);
        }
    }
}
